package com.hsc.sort;

import java.util.Arrays;

/**
 * @author
 * @date 2025-05-24
 * @Description 快速排序算法
定义：快速排序（Quick Sort）：选择一个基准元素，将比基准元素小的元素放在基准元素的左边，比基准元素大的元素放在基准元素的右边，然后递归地对左右两个子序列进行快速排序。
快速排序算法思路：分而治之的思想 二分法
1、选择一个基准值 作为中间标值
2、左边的值比基准值小
3、右边的比基准值大
4、依次递归 再次对上面分好的值再次重复调用
举个生活的例子：手抓一个扑克牌
1、我们随意挑选一个牌作为基准值 参考值
2、然后对扑克牌进行分拣
3、参考基准值 小大分拣到左边 大的分拣到右边
4、此时 基准值的左边一定是都比基准值小的 右边的一定是比基准值大的
5、然后再次左边的分组再次拿一个基准值 对左边的扑克牌进行分拣
右边的分组再次拿一个扑克牌 右边的扑克牌进行分拣 也是左边的小 右边的大
6、...... 不断重复上面的过程 最终整个扑克牌排好序

 */
public class QuickSort {

    public void quickSort(int [] array,int start,int end){
        // 第一次递归调用时候
        // start:0 end:i-1=-1
        if (start > end){
            // 这里必须控制条件 当start > end 时退出
            return;
        }
        // [2,18,12,3,7,5,10]
        int i=start;// 数组开始位置 ，控制从前往后下标
        int j=end;// 数组结束位置 ，控制从后往前的数组下标
        int temp=array[start]; // 基准元素  存储比较的标准

        // 循环条件 i从前往后 j从后往前 如果说不相等 说明元素没有全部比较交换完 说明 i与j 没有碰在一起
        while (i!=j){
            // j 做从后往前的
            // 比较j的位置  往前比较 每次交换一个元素
            // i< j: 表明j从后面一直往前（j--）移动 一直遍历到 i的位置 j一定是大于 i start的位置的 否额数组越界
            // 这个循环是找比基准值小的元素 找到一个比基准值小的元素 会跳出循环 从后往前找 j--
            // array[j]>=temp  说明j的元素会比基准的元素大 需要一直循环 找寻比基准元素小的j
            // demo： 这里temp=2  j-- 当j等于0的时候  i<j 这个条件将不满足 循环结束

            while ( i<j && array[j]>=temp){
                // 第一次循环时时候：
                // i< j :1==0  j=6  满足条件
                // array[j]=10  temp=2  array[j]>=temp 满足条件
                // j--  ：j需要递减
                j--;// 当前元素还是比基准值大  还是满足上条件 需要一直往前挪 一直找到比基准值小的
                // j--  ：j=5 继续循环比较
            }
            // 上面的循环找到了一个j比基准值小的元素 因为我们需要找到比基准值小的元素 然后获取他的位置（这里就是j的位置）
            // 跳出了上面的循环说明找到了一个j 比基准值小的 将元素放在基准值的前面
            // 将确定好位置的j 位置的值 赋值给 array[i] 注意此时 array[i]的值已经 存储在了temp 中
            // 第一次的时候：i=0
            // j的变化：在数组[2,18,12,3,7,5,10] 由于 i=0 也就是元素2  j是从end 开始递减的这里的元素全部都比2 大 一直j-- 到j=0
            // 所以第一次遍历的时候i=0 j=0 将不满足条件
            if (i<j){
                // 如果 i与j的位置还没相等 说明整个数组的前半部分和后半部分 没有完全比完
                array[i]=array[j];
            }

            // 接下来我们找前半部分的元素 如果比我们的基准值大 我们需要将当前的值换到 基准值的后半部分
            // i<j  的作用跟前面的一样 i++ i一直增加 但是一定是小于end的位置 否则数组就会越界
            // array[i]<=temp ：代码作用是 我们需要遍历获取到一个基准值大的元素 作为条件
            // 如果  array[i]<=temp 一直满足条件的话 说明说i位置的值一直都是小于基准值的 不用变化
            while ( i<j && array[i]<=temp){
                i++;// 条件满足 一直往后挪 元素的位置  一直找到比基准值大的
            }
            // 代码走到这里 说明 我们找到了 一个 i的值比基准值大 所以跳出了循环
            // 我们需要将值换到后半部分 在前面的代码中
            // array[j]的值已经存储在array[i]的位置了 所以我们可以将当前i的值赋值给给前面一直空了位置的array[j]
            if (i<j){
                // 如果 i与j的位置还没相等 说明整个数组的前半部分和后半部分 没有完全比完
                array[j]=array[i];
            }

        }
        // 代码至此 一次循环结束 说明i的位置已经到了中间的位置
        array[i]=temp;
        // 打印一下当前数组的
        for (int i1 : array) {
            System.out.print(i1+",");
            // 第一次循环时  i=0 j=0  数组没有任何变化
            // [2,18,12,3,7,5,10]
        }
        System.out.println("");
        // 继续进行递归调用 重复上面的代码操作 此时 我们不需要从整个数组的结尾位置进行比较交换了 因为已经找到了一个中间大小的元素
        // 递归前半部分的代码 i 中间的位置不用定 start的位置不用变化
        // 当第一次递归 的 时候  start:0 end:i-1=-1   quickSort
        quickSort(array,start,i-1);
        // 递归后半部分的代码 end的位置不用变化
        // 第一次执行时： start:0+1=1 end:array.length-1
        // 继续进行递归调用
        quickSort(array,i+1,end);

    }


    public static void main(String[] args) {
        int[] array=new int[]{2,18,12,3,7,5,10};
        QuickSort quickSort=new QuickSort();
        quickSort.quickSort(array,0,array.length-1);
    }
}
